<!DOCTYPE html>
<html lang="zh">
<head>
  <meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=2">
<meta name="theme-color" content="#222">
<meta name="generator" content="Hexo 5.3.0">


  <link rel="apple-touch-icon" sizes="180x180" href="/yuwanzi.io/images/apple-touch-icon-next.png">
  <link rel="icon" type="image/png" sizes="32x32" href="/yuwanzi.io/images/favicon-32x32-next.png">
  <link rel="icon" type="image/png" sizes="16x16" href="/yuwanzi.io/images/favicon-16x16-next.png">
  <link rel="mask-icon" href="/yuwanzi.io/images/logo.svg" color="#222">

<link rel="stylesheet" href="/yuwanzi.io/css/main.css">



<link rel="stylesheet" href="//cdn.jsdelivr.net/npm/@fortawesome/fontawesome-free@5.15.1/css/all.min.css">
  <link rel="stylesheet" href="//cdn.jsdelivr.net/npm/animate.css@3.1.1/animate.min.css">

<script class="hexo-configurations">
    var NexT = window.NexT || {};
    var CONFIG = {"hostname":"suyuhuan.gitee.io","root":"/yuwanzi.io/","images":"/yuwanzi.io/images","scheme":"Muse","version":"8.2.0","exturl":false,"sidebar":{"position":"left","display":"post","padding":18,"offset":12},"copycode":false,"bookmark":{"enable":false,"color":"#222","save":"auto"},"fancybox":false,"mediumzoom":false,"lazyload":false,"pangu":false,"comments":{"style":"tabs","active":null,"storage":true,"lazyload":false,"nav":null},"motion":{"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"fadeInDown","post_body":"fadeInDown","coll_header":"fadeInLeft","sidebar":"fadeInUp"}},"prism":false,"i18n":{"placeholder":"Suche...","empty":"We didn't find any results for the search: ${query}","hits_time":"${hits} results found in ${time} ms","hits":"${hits} results found"}};
  </script>
<meta name="description" content="概述 二叉查找树是一颗有序的二叉树,它有以下性质:  若任意节点的左子树不为空,则左子树上所有节点的值均小于它的根节点的值.   若任意节点的右子树不为空,则右子树上所有节点的值均大于它的根节点的值.   可以将每个链接看做指向另一颗二叉查找树,而这棵树的根节点就是被指向的节点.   没有键值相等的节点.     使用二叉查找树实现的符号表结合了链表插入的灵活性和有序数组查找的高效性.通常采取二叉">
<meta property="og:type" content="article">
<meta property="og:title" content="     《Algorithms,4th Edition》读书笔记-二叉查找树">
<meta property="og:url" content="https://suyuhuan.gitee.io/yuwanzi.io/2017/03/26/2017-3-26-binary_search_tree/index.html">
<meta property="og:site_name" content="玉丸子 | Blog">
<meta property="og:description" content="概述 二叉查找树是一颗有序的二叉树,它有以下性质:  若任意节点的左子树不为空,则左子树上所有节点的值均小于它的根节点的值.   若任意节点的右子树不为空,则右子树上所有节点的值均大于它的根节点的值.   可以将每个链接看做指向另一颗二叉查找树,而这棵树的根节点就是被指向的节点.   没有键值相等的节点.     使用二叉查找树实现的符号表结合了链表插入的灵活性和有序数组查找的高效性.通常采取二叉">
<meta property="og:locale">
<meta property="og:image" content="http://algs4.cs.princeton.edu/32bst/images/binary-tree-anatomy.png">
<meta property="og:image" content="http://algs4.cs.princeton.edu/32bst/images/bst-anatomy.png">
<meta property="og:image" content="http://algs4.cs.princeton.edu/32bst/images/bst-insert.png">
<meta property="og:image" content="http://algs4.cs.princeton.edu/32bst/images/bst-floor.png">
<meta property="og:image" content="http://algs4.cs.princeton.edu/32bst/images/bst-select.png">
<meta property="og:image" content="http://algs4.cs.princeton.edu/32bst/images/bst-delete.png">
<meta property="article:published_time" content="2017-03-26T10:00:00.000Z">
<meta property="article:modified_time" content="2020-11-07T00:58:17.000Z">
<meta property="article:author" content="玉丸子">
<meta property="article:tag" content="2017">
<meta property="article:tag" content="Algorithms">
<meta property="article:tag" content="Tree">
<meta property="article:tag" content="数据结构">
<meta name="twitter:card" content="summary">
<meta name="twitter:image" content="http://algs4.cs.princeton.edu/32bst/images/binary-tree-anatomy.png">


<link rel="canonical" href="https://suyuhuan.gitee.io/yuwanzi.io/2017/03/26/2017-3-26-binary_search_tree/">


<script class="page-configurations">
  // https://hexo.io/docs/variables.html
  CONFIG.page = {
    sidebar: "",
    isHome : false,
    isPost : true,
    lang   : 'zh'
  };
</script>
<title>     《Algorithms,4th Edition》读书笔记-二叉查找树 | 玉丸子 | Blog</title>
  




  <noscript>
  <style>
  body { margin-top: 2rem; }

  .use-motion .menu-item,
  .use-motion .sidebar,
  .use-motion .post-block,
  .use-motion .pagination,
  .use-motion .comments,
  .use-motion .post-header,
  .use-motion .post-body,
  .use-motion .collection-header {
    visibility: visible;
  }

  .use-motion .header,
  .use-motion .site-brand-container .toggle,
  .use-motion .footer { opacity: initial; }

  .use-motion .site-title,
  .use-motion .site-subtitle,
  .use-motion .custom-logo-image {
    opacity: initial;
    top: initial;
  }

  .use-motion .logo-line {
    transform: scaleX(1);
  }

  .search-pop-overlay, .sidebar-nav { display: none; }
  .sidebar-panel { display: block; }
  </style>
</noscript>

<link rel="alternate" href="/yuwanzi.io/atom.xml" title="玉丸子 | Blog" type="application/atom+xml">
</head>

<body itemscope itemtype="http://schema.org/WebPage" class="use-motion">
  <div class="headband"></div>

  <main class="main">
    <header class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-container">
  <div class="site-nav-toggle">
    <div class="toggle" aria-label="Navigationsleiste an/ausschalten" role="button">
    </div>
  </div>

  <div class="site-meta">

    <a href="/yuwanzi.io/" class="brand" rel="start">
      <i class="logo-line"></i>
      <h1 class="site-title">玉丸子 | Blog</h1>
      <i class="logo-line"></i>
    </a>
  </div>

  <div class="site-nav-right">
    <div class="toggle popup-trigger">
    </div>
  </div>
</div>







</div>
        
  
  <div class="toggle sidebar-toggle" role="button">
    <span class="toggle-line"></span>
    <span class="toggle-line"></span>
    <span class="toggle-line"></span>
  </div>

  <aside class="sidebar">

    <div class="sidebar-inner sidebar-nav-active sidebar-toc-active">
      <ul class="sidebar-nav">
        <li class="sidebar-nav-toc">
          Inhaltsverzeichnis
        </li>
        <li class="sidebar-nav-overview">
          Übersicht
        </li>
      </ul>

      <div class="sidebar-panel-container">
        <!--noindex-->
        <div class="post-toc-wrap sidebar-panel">
            <div class="post-toc animated"><ol class="nav"><li class="nav-item nav-level-3"><a class="nav-link" href="#%E6%A6%82%E8%BF%B0"><span class="nav-number">1.</span> <span class="nav-text">概述</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E5%9F%BA%E6%9C%AC%E5%AE%9E%E7%8E%B0"><span class="nav-number">2.</span> <span class="nav-text">基本实现</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E6%9F%A5%E6%89%BE%E4%B8%8E%E6%8F%92%E5%85%A5"><span class="nav-number">3.</span> <span class="nav-text">查找与插入</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#%E6%9F%A5%E6%89%BE"><span class="nav-number">3.1.</span> <span class="nav-text">查找</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#%E6%8F%92%E5%85%A5"><span class="nav-number">3.2.</span> <span class="nav-text">插入</span></a></li></ol></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E6%9C%80%E5%A4%A7%E9%94%AE%E5%92%8C%E6%9C%80%E5%B0%8F%E9%94%AE"><span class="nav-number">4.</span> <span class="nav-text">最大键和最小键</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E5%90%91%E4%B8%8A%E5%8F%96%E6%95%B4%E5%92%8C%E5%90%91%E4%B8%8B%E5%8F%96%E6%95%B4"><span class="nav-number">5.</span> <span class="nav-text">向上取整和向下取整</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E9%80%89%E6%8B%A9%E5%92%8C%E6%8E%92%E5%90%8D"><span class="nav-number">6.</span> <span class="nav-text">选择和排名</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#select"><span class="nav-number">6.1.</span> <span class="nav-text">select</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#rank"><span class="nav-number">6.2.</span> <span class="nav-text">rank</span></a></li></ol></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E5%88%A0%E9%99%A4%E6%9C%80%E5%A4%A7%E9%94%AE%E5%92%8C%E5%88%A0%E9%99%A4%E6%9C%80%E5%B0%8F%E9%94%AE"><span class="nav-number">7.</span> <span class="nav-text">删除最大键和删除最小键</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E5%88%A0%E9%99%A4"><span class="nav-number">8.</span> <span class="nav-text">删除</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E8%8C%83%E5%9B%B4%E6%9F%A5%E6%89%BE"><span class="nav-number">9.</span> <span class="nav-text">范围查找</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E6%80%BB%E7%BB%93"><span class="nav-number">10.</span> <span class="nav-text">总结</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#end"><span class="nav-number">11.</span> <span class="nav-text">end</span></a></li></ol></div>
        </div>
        <!--/noindex-->

        <div class="site-overview-wrap sidebar-panel">
          <div class="site-author site-overview-item animated" itemprop="author" itemscope itemtype="http://schema.org/Person">
  <p class="site-author-name" itemprop="name">玉丸子</p>
  <div class="site-description" itemprop="description">这里是玉丸子的个人博客,与你一起发现更大的世界。</div>
</div>
<div class="site-state-wrap site-overview-item animated">
  <nav class="site-state">
      <div class="site-state-item site-state-posts">
          <a href="/yuwanzi.io/archives">
          <span class="site-state-item-count">68</span>
          <span class="site-state-item-name">Artikel</span>
        </a>
      </div>
      <div class="site-state-item site-state-categories">
            <a href="/yuwanzi.io/categories/">
        <span class="site-state-item-count">39</span>
        <span class="site-state-item-name">Kategorien</span></a>
      </div>
      <div class="site-state-item site-state-tags">
            <a href="/yuwanzi.io/tags/">
        <span class="site-state-item-count">46</span>
        <span class="site-state-item-name">schlagwörter</span></a>
      </div>
  </nav>
</div>



        </div>
      </div>
    </div>
  </aside>
  <div class="sidebar-dimmer"></div>


    </header>

    
  <div class="back-to-top" role="button">
    <i class="fa fa-arrow-up"></i>
    <span>0%</span>
  </div>

<noscript>
  <div class="noscript-warning">Theme NexT works best with JavaScript enabled</div>
</noscript>


    <div class="main-inner post posts-expand">


  


<div class="post-block">
  
  

  <article itemscope itemtype="http://schema.org/Article" class="post-content" lang="zh">
    <link itemprop="mainEntityOfPage" href="https://suyuhuan.gitee.io/yuwanzi.io/2017/03/26/2017-3-26-binary_search_tree/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/yuwanzi.io/images/avatar.gif">
      <meta itemprop="name" content="玉丸子">
      <meta itemprop="description" content="这里是玉丸子的个人博客,与你一起发现更大的世界。">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="玉丸子 | Blog">
    </span>
      <header class="post-header">
        <h1 class="post-title" itemprop="name headline">
               《Algorithms,4th Edition》读书笔记-二叉查找树
        </h1>

        <div class="post-meta-container">
          <div class="post-meta">
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-calendar"></i>
      </span>
      <span class="post-meta-item-text">Veröffentlicht am</span>

      <time title="Erstellt: 2017-03-26 18:00:00" itemprop="dateCreated datePublished" datetime="2017-03-26T18:00:00+08:00">2017-03-26</time>
    </span>
      <span class="post-meta-item">
        <span class="post-meta-item-icon">
          <i class="far fa-calendar-check"></i>
        </span>
        <span class="post-meta-item-text">Bearbeitet am</span>
        <time title="Geändert am: 2020-11-07 08:58:17" itemprop="dateModified" datetime="2020-11-07T08:58:17+08:00">2020-11-07</time>
      </span>
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-folder"></i>
      </span>
      <span class="post-meta-item-text">in</span>
        <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
          <a href="/yuwanzi.io/categories/Algorithms/" itemprop="url" rel="index"><span itemprop="name">Algorithms</span></a>
        </span>
          . 
        <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
          <a href="/yuwanzi.io/categories/Algorithms/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/" itemprop="url" rel="index"><span itemprop="name">数据结构</span></a>
        </span>
          . 
        <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
          <a href="/yuwanzi.io/categories/Algorithms/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/Tree/" itemprop="url" rel="index"><span itemprop="name">Tree</span></a>
        </span>
    </span>

  
</div>

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">
        <h3 id="概述"><a href="#概述" class="headerlink" title="概述"></a>概述</h3><hr>
<p>二叉查找树是一颗<strong>有序的二叉树</strong>,它有以下性质:</p>
<ol>
<li>若任意节点的左子树不为空,则<strong>左子树上所有节点的值均小于它的根节点的值</strong>.</li>
</ol>
<ol start="2">
<li>若任意节点的右子树不为空,则<strong>右子树上所有节点的值均大于它的根节点的值</strong>.</li>
</ol>
<ol start="3">
<li>可以将<strong>每个链接看做指向另一颗二叉查找树</strong>,而这棵树的根节点就是被指向的节点.</li>
</ol>
<ol start="4">
<li>没有键值相等的节点.</li>
</ol>
<p><img src="http://algs4.cs.princeton.edu/32bst/images/binary-tree-anatomy.png"> </p>
<p><img src="http://algs4.cs.princeton.edu/32bst/images/bst-anatomy.png"></p>
<p>使用二叉查找树实现的符号表结合了<strong>链表插入的灵活性和有序数组查找的高效性</strong>.通常采取二叉链表作为存储结构.</p>
<p>每个节点都含有一个键、一个值、一条左链接、一条右链接和一个节点计数器(用于统计其所有子节点数).<strong>左链接指向一棵由小于该节点的所有键组成的二叉查找树,右链接指向一棵由大于该节点的所有键组成的二叉查找树.</strong></p>
<p>如果将一棵二叉查找树的所有键投影到一条直线上,保证一个节点的<strong>左子树中的键出现在它的左边</strong>,<strong>右子树种的键出现在它的右边</strong>,那么我们一定<strong>可以得到一条有序的键列</strong>.</p>
<p>可以说二叉查找树和快速排序很相似.树的根节点就是快速排序中的第一个<code>基准数(切分元素)</code>,左侧的键都比它小,右侧的键都比它大.</p>
<h3 id="基本实现"><a href="#基本实现" class="headerlink" title="基本实现"></a>基本实现</h3><hr>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">BinarySearchTree</span>&lt;<span class="title">K</span> <span class="keyword">extends</span> <span class="title">Comparable</span>&lt;<span class="title">K</span>&gt;, <span class="title">V</span>&gt; </span>&#123;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">private</span> Node root; <span class="comment">// root node</span></span><br><span class="line"></span><br><span class="line">    <span class="keyword">private</span> <span class="class"><span class="keyword">class</span> <span class="title">Node</span> </span>&#123;</span><br><span class="line">        <span class="keyword">private</span> K key;</span><br><span class="line">        <span class="keyword">private</span> V value;</span><br><span class="line">        <span class="keyword">private</span> Node left, right; <span class="comment">// left and right subtree</span></span><br><span class="line">        <span class="keyword">private</span> <span class="keyword">int</span> size; <span class="comment">// number of nodes in subtree</span></span><br><span class="line"></span><br><span class="line">        <span class="function"><span class="keyword">public</span> <span class="title">Node</span><span class="params">(K key, V value, <span class="keyword">int</span> size)</span> </span>&#123;</span><br><span class="line">            <span class="keyword">this</span>.key = key;</span><br><span class="line">            <span class="keyword">this</span>.value = value;</span><br><span class="line">            <span class="keyword">this</span>.size = size;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">	</span><br><span class="line">	<span class="comment">/**</span></span><br><span class="line"><span class="comment">     * Returns true if this symbol table is empty.</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@return</span> &#123;<span class="doctag">@code</span> true&#125; is this symbol table is empty, &#123;<span class="doctag">@code</span> false&#125; otherwise.</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">isEmpty</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        <span class="keyword">return</span> size() == <span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * Returns the number of key-value pairs in this symbol table.</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@return</span> the number of key-value pairs in this symbol table.</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">size</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        <span class="keyword">return</span> size(root);</span><br><span class="line">    &#125;</span><br><span class="line">	</span><br><span class="line">	<span class="comment">// return number of key-value pairs in binary search tree rooted at x</span></span><br><span class="line">    <span class="function"><span class="keyword">private</span> <span class="keyword">int</span> <span class="title">size</span><span class="params">(Node x)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (x == <span class="keyword">null</span>) <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">        <span class="keyword">else</span> <span class="keyword">return</span> x.size;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;	</span><br></pre></td></tr></table></figure>
<p>在以上代码中,使用私有嵌套类<code>Node</code>来表示一个二叉链表,每个<code>Node</code>对象都是一棵含有N个节点的子树的根节点.变量<code>root</code>指向二叉查找树的根节点(这棵树包含了符号表中的所有键值对).</p>
<h3 id="查找与插入"><a href="#查找与插入" class="headerlink" title="查找与插入"></a>查找与插入</h3><hr>
<h4 id="查找"><a href="#查找" class="headerlink" title="查找"></a>查找</h4><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment">    * Returns the value associated with the given key.</span></span><br><span class="line"><span class="comment">    *</span></span><br><span class="line"><span class="comment">    * <span class="doctag">@param</span> key the key</span></span><br><span class="line"><span class="comment">    * <span class="doctag">@return</span> the value associated with the given key if the key is in the symbol table</span></span><br><span class="line"><span class="comment">    * and &#123;<span class="doctag">@code</span> null&#125; if the key is not in the symbol table.</span></span><br><span class="line"><span class="comment">    * <span class="doctag">@throws</span> IllegalArgumentException if &#123;<span class="doctag">@code</span> key&#125; is &#123;<span class="doctag">@code</span> null&#125;</span></span><br><span class="line"><span class="comment">    */</span></span><br><span class="line">   <span class="function"><span class="keyword">public</span> V <span class="title">get</span><span class="params">(K key)</span> </span>&#123;</span><br><span class="line">       <span class="keyword">if</span> (key == <span class="keyword">null</span>)</span><br><span class="line">           <span class="keyword">throw</span> <span class="keyword">new</span> IllegalArgumentException(<span class="string">&quot;called get() with a null key.&quot;</span>);</span><br><span class="line">       <span class="keyword">return</span> get(root, key);</span><br><span class="line">   &#125;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line">   <span class="function"><span class="keyword">private</span> V <span class="title">get</span><span class="params">(Node x, K key)</span> </span>&#123;</span><br><span class="line">       <span class="keyword">if</span> (x == <span class="keyword">null</span>) <span class="keyword">return</span> <span class="keyword">null</span>;</span><br><span class="line">       <span class="keyword">int</span> cmp = key.compareTo(x.key);</span><br><span class="line">       <span class="keyword">if</span> (cmp &lt; <span class="number">0</span>) &#123;</span><br><span class="line">           <span class="comment">// if key &lt; x.key , search left subtree</span></span><br><span class="line">           <span class="keyword">return</span> get(x.left, key);</span><br><span class="line">       &#125; <span class="keyword">else</span> <span class="keyword">if</span> (cmp &gt; <span class="number">0</span>) &#123;</span><br><span class="line">           <span class="comment">// if key &gt; x.key , search right subtree</span></span><br><span class="line">           <span class="keyword">return</span> get(x.right, key);</span><br><span class="line">       &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">           <span class="comment">// hit target</span></span><br><span class="line">           <span class="keyword">return</span> x.value;</span><br><span class="line">       &#125;</span><br><span class="line">   &#125;</span><br></pre></td></tr></table></figure>
<p>在二叉查找树中实现查找操作是很简单而简洁的,这也是二叉查找树的特性之一.-<strong>如果树为空,就返回null,如果被查找的键小于根节点的键,我们就继续在左子树中查找,否则在右子树中查找.</strong></p>
<h4 id="插入"><a href="#插入" class="headerlink" title="插入"></a>插入</h4><p>插入操作的逻辑与查找差不多,只不过需要在<strong>判定树为空时,返回一个含有该键值对的新节点,还需要重置搜索路径上每个父节点指向子节点的链接,并增加路径上每个节点中的子节点计数器的值</strong>.</p>
<p><img src="http://algs4.cs.princeton.edu/32bst/images/bst-insert.png"></p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment">     * Inserts the specified key-value pair into  the symbol table.</span></span><br><span class="line"><span class="comment">     * overwriting the old value with the new value if the symbol table already contains</span></span><br><span class="line"><span class="comment">     * the specified key.</span></span><br><span class="line"><span class="comment">     * Deletes the specified key (and its associated value) from this symbol table</span></span><br><span class="line"><span class="comment">     * if the specified value is &#123;<span class="doctag">@code</span> null&#125;.</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> key   the key</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> value the value</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@throws</span> IllegalArgumentException if &#123;<span class="doctag">@code</span> key&#125; is &#123;<span class="doctag">@code</span> null&#125;.</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">put</span><span class="params">(K key, V value)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (key == <span class="keyword">null</span>)</span><br><span class="line">            <span class="keyword">throw</span> <span class="keyword">new</span> IllegalArgumentException(<span class="string">&quot;called put() with a null key.&quot;</span>);</span><br><span class="line">        <span class="keyword">if</span> (value == <span class="keyword">null</span>) &#123;</span><br><span class="line">            delete(key);</span><br><span class="line">            <span class="keyword">return</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        root = put(root, key, value);</span><br><span class="line">        <span class="function"><span class="keyword">assert</span> <span class="title">check</span><span class="params">()</span></span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">private</span> Node <span class="title">put</span><span class="params">(Node x, K key, V value)</span> </span>&#123;</span><br><span class="line">        <span class="comment">// if tree is empty, return a new node.</span></span><br><span class="line">        <span class="keyword">if</span> (x == <span class="keyword">null</span>) <span class="keyword">return</span> <span class="keyword">new</span> Node(key, value, <span class="number">1</span>);</span><br><span class="line"></span><br><span class="line">        <span class="keyword">int</span> cmp = key.compareTo(x.key);</span><br><span class="line">        <span class="keyword">if</span> (cmp &lt; <span class="number">0</span>) &#123;</span><br><span class="line">            x.left = put(x.left, key, value);</span><br><span class="line">        &#125; <span class="keyword">else</span> <span class="keyword">if</span> (cmp &gt; <span class="number">0</span>) &#123;</span><br><span class="line">            x.right = put(x.right, key, value);</span><br><span class="line">        &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">            <span class="comment">// hit target,overwriting old value with the new value</span></span><br><span class="line">            x.value = value;</span><br><span class="line">        &#125;</span><br><span class="line">        x.size = <span class="number">1</span> + size(x.left) + size(x.right); <span class="comment">// compute subtree node size</span></span><br><span class="line">        <span class="keyword">return</span> x;</span><br><span class="line">    &#125;</span><br></pre></td></tr></table></figure>
<h3 id="最大键和最小键"><a href="#最大键和最小键" class="headerlink" title="最大键和最小键"></a>最大键和最小键</h3><hr>
<ul>
<li>如果根节点的<strong>左链接为空</strong>,那么一棵二叉查找树中<strong>最小的键就是根节点</strong>.</li>
</ul>
<ul>
<li>如果<strong>左链接非空</strong>,那么树中的<strong>最小键就是左子树中的最小键</strong>.找出最大键的逻辑也是类似的,只是变为查找右子树而已.</li>
</ul>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment">  * Returns the smallest key in the symbol table.</span></span><br><span class="line"><span class="comment">  *</span></span><br><span class="line"><span class="comment">  * <span class="doctag">@return</span> the smallest key in the symbol table.</span></span><br><span class="line"><span class="comment">  * <span class="doctag">@throws</span> NoSuchElementException if the symbol table is empty</span></span><br><span class="line"><span class="comment">  */</span></span><br><span class="line"> <span class="function"><span class="keyword">public</span> K <span class="title">min</span><span class="params">()</span> </span>&#123;</span><br><span class="line">     <span class="keyword">if</span> (isEmpty())</span><br><span class="line">         <span class="keyword">throw</span> <span class="keyword">new</span> NoSuchElementException(<span class="string">&quot;called min() with empty symbol table.&quot;</span>);</span><br><span class="line">     <span class="keyword">return</span> min(root).key;</span><br><span class="line"> &#125;</span><br><span class="line"></span><br><span class="line"> <span class="function"><span class="keyword">private</span> Node <span class="title">min</span><span class="params">(Node x)</span> </span>&#123;</span><br><span class="line">     <span class="keyword">if</span> (x.left == <span class="keyword">null</span>) <span class="keyword">return</span> x;</span><br><span class="line">     <span class="keyword">else</span> <span class="keyword">return</span> min(x.left);</span><br><span class="line"> &#125;</span><br><span class="line"></span><br><span class="line"> <span class="comment">/**</span></span><br><span class="line"><span class="comment">  * Returns the largest key in the symbol table.</span></span><br><span class="line"><span class="comment">  *</span></span><br><span class="line"><span class="comment">  * <span class="doctag">@return</span> the largest key in the symbol table.</span></span><br><span class="line"><span class="comment">  * <span class="doctag">@throws</span> NoSuchElementException if the symbol table is empty</span></span><br><span class="line"><span class="comment">  */</span></span><br><span class="line"> <span class="function"><span class="keyword">public</span> K <span class="title">max</span><span class="params">()</span> </span>&#123;</span><br><span class="line">     <span class="keyword">if</span> (isEmpty())</span><br><span class="line">         <span class="keyword">throw</span> <span class="keyword">new</span> NoSuchElementException(<span class="string">&quot;called max() with empty symbol table.&quot;</span>);</span><br><span class="line">     <span class="keyword">return</span> max(root).key;</span><br><span class="line"> &#125;</span><br><span class="line"></span><br><span class="line"> <span class="function"><span class="keyword">private</span> Node <span class="title">max</span><span class="params">(Node x)</span> </span>&#123;</span><br><span class="line">     <span class="keyword">if</span> (x.right == <span class="keyword">null</span>) <span class="keyword">return</span> x;</span><br><span class="line">     <span class="keyword">else</span> <span class="keyword">return</span> max(x.right);</span><br><span class="line"> &#125;</span><br></pre></td></tr></table></figure>
<h3 id="向上取整和向下取整"><a href="#向上取整和向下取整" class="headerlink" title="向上取整和向下取整"></a>向上取整和向下取整</h3><hr>
<p><img src="http://algs4.cs.princeton.edu/32bst/images/bst-floor.png" alt="向下取整的路径轨迹"></p>
<ul>
<li>如果给定的键<strong>key小于二叉查找树的根节点的键</strong>,那么小于等于key的最大键<code>floor(key)</code><strong>一定在根节点的左子树中</strong>.</li>
</ul>
<ul>
<li>如果给定的键<strong>key大于二叉查找树的根节点</strong>,那么<strong>只有当根节点右子树中存在小于等于key的节点时,小于等于key的最大键才会出现在右子树中,否则根节点就是小于等于key的最大键</strong>.(将左变为右,小于变为大于就是向上取整的实现逻辑)</li>
</ul>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> K <span class="title">floor</span><span class="params">(K key)</span> </span>&#123;</span><br><span class="line">       <span class="keyword">if</span> (key == <span class="keyword">null</span>)</span><br><span class="line">           <span class="keyword">throw</span> <span class="keyword">new</span> IllegalArgumentException(<span class="string">&quot;called floor() with a null key.&quot;</span>);</span><br><span class="line">       <span class="keyword">if</span> (isEmpty())</span><br><span class="line">           <span class="keyword">throw</span> <span class="keyword">new</span> NoSuchElementException(<span class="string">&quot;called floor() with empty symbol table.&quot;</span>);</span><br><span class="line">       Node x = floor(root, key);</span><br><span class="line">       <span class="keyword">if</span> (x == <span class="keyword">null</span>) <span class="keyword">return</span> <span class="keyword">null</span>;</span><br><span class="line">       <span class="keyword">else</span> <span class="keyword">return</span> x.key;</span><br><span class="line">   &#125;</span><br><span class="line"></span><br><span class="line">   <span class="function"><span class="keyword">private</span> Node <span class="title">floor</span><span class="params">(Node x, K key)</span> </span>&#123;</span><br><span class="line">       <span class="keyword">if</span> (x == <span class="keyword">null</span>) <span class="keyword">return</span> <span class="keyword">null</span>;</span><br><span class="line"></span><br><span class="line">       <span class="keyword">int</span> cmp = key.compareTo(x.key);</span><br><span class="line">       <span class="keyword">if</span> (cmp == <span class="number">0</span>) <span class="keyword">return</span> x;</span><br><span class="line">       <span class="keyword">if</span> (cmp &lt; <span class="number">0</span>) <span class="keyword">return</span> floor(x.left, key);</span><br><span class="line">       Node t = floor(x.right, key);</span><br><span class="line">       <span class="keyword">if</span> (t != <span class="keyword">null</span>) <span class="keyword">return</span> t;</span><br><span class="line">       <span class="keyword">else</span> <span class="keyword">return</span> x;</span><br><span class="line">   &#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> K <span class="title">ceiling</span><span class="params">(K key)</span> </span>&#123;</span><br><span class="line">       <span class="keyword">if</span> (key == <span class="keyword">null</span>)</span><br><span class="line">           <span class="keyword">throw</span> <span class="keyword">new</span> IllegalArgumentException(<span class="string">&quot;called ceiling() with a null key.&quot;</span>);</span><br><span class="line">       <span class="keyword">if</span> (isEmpty())</span><br><span class="line">           <span class="keyword">throw</span> <span class="keyword">new</span> NoSuchElementException(<span class="string">&quot;called ceiling() with empty symbol table.&quot;</span>);</span><br><span class="line">       Node x = ceiling(root, key);</span><br><span class="line">       <span class="keyword">if</span> (x == <span class="keyword">null</span>) <span class="keyword">return</span> <span class="keyword">null</span>;</span><br><span class="line">       <span class="keyword">else</span> <span class="keyword">return</span> x.key;</span><br><span class="line">   &#125;</span><br><span class="line"></span><br><span class="line">   <span class="function"><span class="keyword">private</span> Node <span class="title">ceiling</span><span class="params">(Node x, K key)</span> </span>&#123;</span><br><span class="line">       <span class="keyword">if</span> (x == <span class="keyword">null</span>) <span class="keyword">return</span> <span class="keyword">null</span>;</span><br><span class="line"></span><br><span class="line">       <span class="keyword">int</span> cmp = key.compareTo(x.key);</span><br><span class="line">       <span class="keyword">if</span> (cmp == <span class="number">0</span>) <span class="keyword">return</span> x;</span><br><span class="line">       <span class="keyword">if</span> (cmp &lt; <span class="number">0</span>) &#123;</span><br><span class="line">           Node t = ceiling(x.left, key);</span><br><span class="line">           <span class="keyword">if</span> (t != <span class="keyword">null</span>) <span class="keyword">return</span> t;</span><br><span class="line">           <span class="keyword">else</span> <span class="keyword">return</span> x;</span><br><span class="line">       &#125;</span><br><span class="line">       <span class="keyword">return</span> ceiling(x.right, key);</span><br><span class="line">   &#125;</span><br></pre></td></tr></table></figure>
<h3 id="选择和排名"><a href="#选择和排名" class="headerlink" title="选择和排名"></a>选择和排名</h3><hr>
<h4 id="select"><a href="#select" class="headerlink" title="select"></a>select</h4><p>假设我们想找到排名为<code>k</code>的键(即树中正好有k个小于它的键).</p>
<ul>
<li>如果<strong>左子树中的节点数<code>t</code>大于<code>k</code></strong>,那么我们就继续递归地<strong>在左子树中查找排名为<code>k</code>的键</strong>.</li>
</ul>
<ul>
<li><strong>如果<code>t</code>等于<code>k</code></strong>,我们就<strong>返回根节点中的键</strong>.</li>
</ul>
<ul>
<li><strong>如果<code>t</code>小于<code>k</code></strong>,我们就递归地<strong>在右子树中查找排名为<code>(k-t-1)</code>的键</strong>.</li>
</ul>
<p><img src="http://algs4.cs.princeton.edu/32bst/images/bst-select.png" alt="选择操作路径轨迹"></p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> K <span class="title">select</span><span class="params">(<span class="keyword">int</span> k)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (k &lt; <span class="number">0</span> || k &gt;= size())</span><br><span class="line">        <span class="keyword">throw</span> <span class="keyword">new</span> IllegalArgumentException(<span class="string">&quot;called select() with invalid argument: &quot;</span> + k);</span><br><span class="line">    <span class="keyword">return</span> select(root, k).key;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">private</span> Node <span class="title">select</span><span class="params">(Node x, <span class="keyword">int</span> k)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (x == <span class="keyword">null</span>) <span class="keyword">return</span> <span class="keyword">null</span>;</span><br><span class="line">    <span class="keyword">int</span> t = size(x.left);</span><br><span class="line">    <span class="comment">// if left subtree node size greater than k,in left subtree search</span></span><br><span class="line">    <span class="keyword">if</span> (t &gt; k) <span class="keyword">return</span> select(x.left, k);</span><br><span class="line">        <span class="comment">// otherwise,in right subtree search</span></span><br><span class="line">    <span class="keyword">else</span> <span class="keyword">if</span> (t &lt; k) <span class="keyword">return</span> select(x.right, k - t - <span class="number">1</span>);</span><br><span class="line">    <span class="keyword">else</span> <span class="keyword">return</span> x;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h4 id="rank"><a href="#rank" class="headerlink" title="rank"></a>rank</h4><p><code>rank()</code>函数是<code>select()</code>函数的逆函数,它会返回指定键的排名.</p>
<ul>
<li>如果给定的<strong>键和根节点的键相等</strong>,就<strong>返回左子树中的节点总数t</strong>.</li>
</ul>
<ul>
<li>如果给定的<strong>键小于根节点</strong>,就<strong>返回该键在左子树中的排名</strong>(递归计算).</li>
</ul>
<ul>
<li>如果给定的<strong>键大于根节点</strong>,就<strong>返回<code>t+1(根节点)</code>加上它在右子树中的排名</strong>(递归计算).</li>
</ul>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">rank</span><span class="params">(K key)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (key == <span class="keyword">null</span>)</span><br><span class="line">        <span class="keyword">throw</span> <span class="keyword">new</span> IllegalArgumentException(<span class="string">&quot;called rank() with a null key.&quot;</span>);</span><br><span class="line">    <span class="keyword">return</span> rank(root, key);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">private</span> <span class="keyword">int</span> <span class="title">rank</span><span class="params">(Node x, K key)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (x == <span class="keyword">null</span>) <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">int</span> cmp = key.compareTo(x.key);</span><br><span class="line">    <span class="keyword">if</span> (cmp &lt; <span class="number">0</span>)</span><br><span class="line">        <span class="keyword">return</span> rank(x.left, key);</span><br><span class="line">    <span class="keyword">else</span> <span class="keyword">if</span> (cmp &gt; <span class="number">0</span>)</span><br><span class="line">        <span class="keyword">return</span> <span class="number">1</span> + size(x.left) + rank(x.right, key);</span><br><span class="line">    <span class="keyword">else</span></span><br><span class="line">        <span class="keyword">return</span> size(x.left);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h3 id="删除最大键和删除最小键"><a href="#删除最大键和删除最小键" class="headerlink" title="删除最大键和删除最小键"></a>删除最大键和删除最小键</h3><hr>
<p>对于删除最小键,需要不断深入根节点的左子树<strong>直至遇见一个空链接</strong>,然后将指向该节点的链接指向该节点的右子树(只需要在递归调用中返回它的右链接即可).此时已经没有任何链接指向要被删除的节点,因此它会被垃圾回收器gc掉.</p>
<p>删除最大键与其逻辑相似,只是方向相反.</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * Removes the smallest key and associated value from the symbol table.</span></span><br><span class="line"><span class="comment"> *</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@throws</span> NoSuchElementException if the symbol table is empty.</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">deleteMin</span><span class="params">()</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (isEmpty())</span><br><span class="line">        <span class="keyword">throw</span> <span class="keyword">new</span> NoSuchElementException(<span class="string">&quot;Symbol table underflow.&quot;</span>);</span><br><span class="line">    root = deleteMin(root);</span><br><span class="line">    <span class="function"><span class="keyword">assert</span> <span class="title">check</span><span class="params">()</span></span>;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">private</span> Node <span class="title">deleteMin</span><span class="params">(Node x)</span> </span>&#123;</span><br><span class="line">    <span class="comment">// if the left link is empty,will link to the node of the right subtree.</span></span><br><span class="line">    <span class="keyword">if</span> (x.left == <span class="keyword">null</span>) <span class="keyword">return</span> x.right;</span><br><span class="line"></span><br><span class="line">    x.left = deleteMin(x.left);</span><br><span class="line">    x.size = size(x.left) + size(x.right) + <span class="number">1</span>;</span><br><span class="line">    <span class="keyword">return</span> x;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * Removes the largest key and associated value from the symbol table.</span></span><br><span class="line"><span class="comment"> *</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@throws</span> NoSuchElementException if the symbol table is empty</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">deleteMax</span><span class="params">()</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (isEmpty())</span><br><span class="line">        <span class="keyword">throw</span> <span class="keyword">new</span> NoSuchElementException(<span class="string">&quot;Symbol table underflow.&quot;</span>);</span><br><span class="line">    root = deleteMax(root);</span><br><span class="line">    <span class="function"><span class="keyword">assert</span> <span class="title">check</span><span class="params">()</span></span>;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">private</span> Node <span class="title">deleteMax</span><span class="params">(Node x)</span> </span>&#123;</span><br><span class="line">    <span class="comment">// if the right link is empty,will link to the node of the left subtree.</span></span><br><span class="line">    <span class="keyword">if</span> (x.right == <span class="keyword">null</span>) <span class="keyword">return</span> x.left;</span><br><span class="line"></span><br><span class="line">    x.right = deleteMax(x.right);</span><br><span class="line">    x.size = size(x.left) + size(x.right) + <span class="number">1</span>;</span><br><span class="line">    <span class="keyword">return</span> x;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h3 id="删除"><a href="#删除" class="headerlink" title="删除"></a>删除</h3><hr>
<p>删除操作是二叉查找树中较为复杂的操作,假设我们要删除节点<code>x</code>(它是一个拥有两个子节点的节点),基本的实现逻辑如下.</p>
<ul>
<li><p>在删除节点<code>x</code>后用它的后继节点填补它的位置.</p>
</li>
<li><p>找出<code>x</code>的<strong>右子树中的最小节点</strong>(这样替换仍能保证树的有序性,因为<code>x.key</code>和它的后继节点的键之间不存在其他的键)做为<code>x</code>的后继节点.</p>
</li>
</ul>
<ul>
<li>将由此节点到根节点的路径上的所有节点的计数器减1(这里计数器的值仍然会被设为其所有子树中的节点总数加1).</li>
</ul>
<p><img src="http://algs4.cs.princeton.edu/32bst/images/bst-delete.png"></p>
<p>具体的过程如以下例子:</p>
<ol>
<li>将指向即将被删除的节点的链接保存为<code>t</code>.</li>
</ol>
<ol start="2">
<li>将<code>x</code>指向它的后继节点<code>min(t.right)</code>.</li>
</ol>
<ol start="3">
<li>将<code>x</code>的右链接(原本指向一棵所有节点都大于<code>x.key</code>的二叉查找树)指向<code>deleteMin(t.right)</code>,也就是在删除后所有的节点仍然都大于<code>x.key</code>的子二叉查找树.</li>
</ol>
<ol start="4">
<li>将<code>x</code>的左链接(本为空)指向<code>t.left</code>(其下所有的键都小于被删除的节点和它的后继节点).</li>
</ol>
<p>以上的实现逻辑有一个缺点,即是<strong>在某些实际应用场景下会产生性能问题</strong>,主要原因<strong>在于后继节点是一个随意的决定,且没有考虑树的对称性</strong>.</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">delete</span><span class="params">(K key)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (key == <span class="keyword">null</span>)</span><br><span class="line">        <span class="keyword">throw</span> <span class="keyword">new</span> IllegalArgumentException(<span class="string">&quot;called delete() with a null key.&quot;</span>);</span><br><span class="line">    root = delete(root, key);</span><br><span class="line">    <span class="function"><span class="keyword">assert</span> <span class="title">check</span><span class="params">()</span></span>;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">private</span> Node <span class="title">delete</span><span class="params">(Node x, K key)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (x == <span class="keyword">null</span>) <span class="keyword">return</span> <span class="keyword">null</span>;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">int</span> cmp = key.compareTo(x.key);</span><br><span class="line">    <span class="keyword">if</span> (cmp &lt; <span class="number">0</span>)</span><br><span class="line">        x.left = delete(x.left, key);</span><br><span class="line">    <span class="keyword">else</span> <span class="keyword">if</span> (cmp &gt; <span class="number">0</span>)</span><br><span class="line">        x.right = delete(x.right, key);</span><br><span class="line">    <span class="keyword">else</span> &#123;</span><br><span class="line">        <span class="keyword">if</span> (x.right == <span class="keyword">null</span>)</span><br><span class="line">            <span class="keyword">return</span> x.left;</span><br><span class="line">        <span class="keyword">if</span> (x.left == <span class="keyword">null</span>)</span><br><span class="line">            <span class="keyword">return</span> x.right;</span><br><span class="line">        Node t = x;</span><br><span class="line">        x = min(t.right);</span><br><span class="line">        x.right = deleteMin(t.right);</span><br><span class="line">        x.left = t.left;</span><br><span class="line">    &#125;</span><br><span class="line">    x.size = size(x.left) + size(x.right) + <span class="number">1</span>;</span><br><span class="line">    <span class="keyword">return</span> x;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h3 id="范围查找"><a href="#范围查找" class="headerlink" title="范围查找"></a>范围查找</h3><hr>
<p>实现一个范围查找的思路可以是:<strong>将所有落在给定范围以内的键放入一个队列<code>Queue</code>并跳过那些不可能含有所查找键的子树</strong>.</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> Iterable&lt;K&gt; <span class="title">keys</span><span class="params">(K lo, K hi)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (lo == <span class="keyword">null</span>)</span><br><span class="line">        <span class="keyword">throw</span> <span class="keyword">new</span> IllegalArgumentException(<span class="string">&quot;called keys(lo,hi) first argument is null.&quot;</span>);</span><br><span class="line">    <span class="keyword">if</span> (hi == <span class="keyword">null</span>)</span><br><span class="line">        <span class="keyword">throw</span> <span class="keyword">new</span> IllegalArgumentException(<span class="string">&quot;called keys(lo,hi) second argument is null.&quot;</span>);</span><br><span class="line"></span><br><span class="line">    Queue&lt;K&gt; queue = <span class="keyword">new</span> Queue&lt;K&gt;();</span><br><span class="line">    keys(root, queue, lo, hi);</span><br><span class="line">    <span class="keyword">return</span> queue;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">private</span> <span class="keyword">void</span> <span class="title">keys</span><span class="params">(Node x, Queue&lt;K&gt; queue, K lo, K hi)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (x == <span class="keyword">null</span>) <span class="keyword">return</span>;</span><br><span class="line">    <span class="keyword">int</span> cmp_lo = lo.compareTo(x.key);</span><br><span class="line">    <span class="keyword">int</span> cmp_hi = hi.compareTo(x.key);</span><br><span class="line">    <span class="keyword">if</span> (cmp_lo &lt; <span class="number">0</span>)</span><br><span class="line">        keys(x.left, queue, lo, hi);</span><br><span class="line">    <span class="keyword">if</span> (cmp_lo &lt;= <span class="number">0</span> &amp;&amp; cmp_hi &gt;= <span class="number">0</span>)</span><br><span class="line">        queue.enqueue(x.key);</span><br><span class="line">    <span class="keyword">if</span> (cmp_hi &gt; <span class="number">0</span>)</span><br><span class="line">        keys(x.right, queue, lo, hi);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h3 id="总结"><a href="#总结" class="headerlink" title="总结"></a>总结</h3><hr>
<p>二叉查找树的高度决定了它在最坏情况下的运行效率,但由于键的插入顺序不会是永远随机的,所以树的某一端高度可能会非常深,解决这个问题可以使用平衡二叉查找树,它能保证无论键的插入顺序如何,树的高度都将是总键数的对数.</p>
<p>本文中的实现皆采用递归的方式是为了提高可读性,二叉查找树可以使用非递归的方式实现且效率会更高.</p>
<p>二叉查找树结合了链表插入操作的灵活性和有序数组查找操作的高效性,且还有很多种优化的改进方案(例如平衡二叉查找树),总体来说二叉查找树是一种比较好的动态查找方法.</p>
<h3 id="end"><a href="#end" class="headerlink" title="end"></a>end</h3><hr>
<ul>
<li>Author : <a target="_blank" rel="noopener" href="https://github.com/SylvanasSun">SylvanasSun</a></li>
</ul>
<ul>
<li>Email : <a href="mailto:&#x73;&#x79;&#108;&#x76;&#97;&#x6e;&#97;&#115;&#x73;&#117;&#x6e;&#x5f;&#x78;&#116;&#x7a;&#64;&#49;&#54;&#51;&#x2e;&#x63;&#111;&#109;">&#x73;&#x79;&#108;&#x76;&#97;&#x6e;&#97;&#115;&#x73;&#117;&#x6e;&#x5f;&#x78;&#116;&#x7a;&#64;&#49;&#54;&#51;&#x2e;&#x63;&#111;&#109;</a></li>
</ul>
<ul>
<li>文中的完整实现代码见我的<a target="_blank" rel="noopener" href="https://github.com/SylvanasSun/algs4-study">GitHub</a> &amp; <a target="_blank" rel="noopener" href="https://gist.github.com/SylvanasSun/c4bddf50d94148470c0836af64449e8b">Gist</a></li>
</ul>
<ul>
<li>本文参考资料引用自<a target="_blank" rel="noopener" href="http://algs4.cs.princeton.edu/32bst/">&lt;&lt;Algorithms,4th Edition&gt;&gt;</a> &amp; <a target="_blank" rel="noopener" href="https://zh.wikipedia.org/wiki/%E4%BA%8C%E5%85%83%E6%90%9C%E5%B0%8B%E6%A8%B9">WikiPedia</a></li>
</ul>

    </div>

    
    
    

    <footer class="post-footer">
          <div class="post-tags">
              <a href="/yuwanzi.io/tags/2017/" rel="tag"># 2017</a>
              <a href="/yuwanzi.io/tags/Algorithms/" rel="tag"># Algorithms</a>
              <a href="/yuwanzi.io/tags/Tree/" rel="tag"># Tree</a>
              <a href="/yuwanzi.io/tags/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/" rel="tag"># 数据结构</a>
          </div>

        

          <div class="post-nav">
            <div class="post-nav-item">
                <a href="/yuwanzi.io/2017/03/20/2017-3-20-sorting_algorithm/" rel="prev" title="谈谈几个常用的排序算法">
                  <i class="fa fa-chevron-left"></i> 谈谈几个常用的排序算法
                </a>
            </div>
            <div class="post-nav-item">
                <a href="/yuwanzi.io/2017/03/28/2017-3-28-2_3tree/" rel="next" title="《Algorithms,4th Edition》读书笔记-2-3查找树">
                  《Algorithms,4th Edition》读书笔记-2-3查找树 <i class="fa fa-chevron-right"></i>
                </a>
            </div>
          </div>
    </footer>
  </article>
</div>







<script>
  window.addEventListener('tabs:register', () => {
    let { activeClass } = CONFIG.comments;
    if (CONFIG.comments.storage) {
      activeClass = localStorage.getItem('comments_active') || activeClass;
    }
    if (activeClass) {
      const activeTab = document.querySelector(`a[href="#comment-${activeClass}"]`);
      if (activeTab) {
        activeTab.click();
      }
    }
  });
  if (CONFIG.comments.storage) {
    window.addEventListener('tabs:click', event => {
      if (!event.target.matches('.tabs-comment .tab-content .tab-pane')) return;
      const commentClass = event.target.classList[1];
      localStorage.setItem('comments_active', commentClass);
    });
  }
</script>
</div>
  </main>

  <footer class="footer">
    <div class="footer-inner">


<div class="copyright">
  &copy; 
  <span itemprop="copyrightYear">2021</span>
  <span class="with-love">
    <i class="fa fa-heart"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">玉丸子</span>
</div>
  <div class="powered-by">Erstellt mit  <a href="https://hexo.io/" class="theme-link" rel="noopener" target="_blank">Hexo</a> & <a href="https://theme-next.js.org/muse/" class="theme-link" rel="noopener" target="_blank">NexT.Muse</a>
  </div>

    </div>
  </footer>

  
  <script src="//cdn.jsdelivr.net/npm/animejs@3.2.1/lib/anime.min.js"></script>
<script src="/yuwanzi.io/js/utils.js"></script><script src="/yuwanzi.io/js/motion.js"></script><script src="/yuwanzi.io/js/schemes/muse.js"></script><script src="/yuwanzi.io/js/next-boot.js"></script>

  






  





</body>
</html>
